package array;

/**
 * 给出多个区间，计算这些区间的区间和
 * @author liumingju
 * @date 2025/3/19 19:15
 */
public class 区间和 {

    public static void main(String[] args) {
        int[] target = {1,2,3,4,5,6};
        int sum = sum(2, 4, target);
        System.out.println(sum);
    }


    /**
     * 暴力解法 直接for循环。但是极端情况下，时间复杂度为O(n^2)
     * @return
     */
    public static int sum(int begin,int right,int[] target){
        int res = 0;
        for(;begin<=right;begin++){
            res=target[begin]+res;
        }
        return res;
    }

    /**
     * 空间换时间，sum[i] = target[i]+target[i-1]+...+target[0]
     * 区间[i,j]的和=sum[j]-sum[i]
     * 此种算法适合一次性算多个独立区间的场景（前缀和）
     * @param begin
     * @param right
     * @param target
     * @return
     */
    public static int sum01(int begin,int right,int[] target){
        return 0;
    }
}
